This invention relates in general to the field of optimization systems and methods, and more particularly to a system and method for optimizing the allocation of a resource.
Many businesses and other types of organizations wish to optimize the manner in which they allocate various resources to reduce costs and improve efficiency. For example, a shipper of goods might wish to optimize the allocation of transportation capacity among multiple competing carriers in a way that minimizes shipping costs while satisfying the shipper""s coverage, equipment, service, and other requirements. It is often desirable to optimize the allocation of such resources using computer-based systems that incorporate software specifically tailored to solve optimization problems using standard xe2x80x9cbrute forcexe2x80x9d approaches. For example, commercially available integer program solvers such as CPLEX and XPRESS may in some circumstances be used in an attempt to optimize a shipper""s allocation of transportation capacity.
As the resource allocation needs of business and other organizations continue to increase in their complexity and importance, the speed, efficiency, and accuracy in which resources are allocated have become increasingly critical to the success of the organizations. However, previous systems and methods for optimizing the allocation of resources are inadequate for many optimization scenarios. For example, integer program solvers such as CPLEX and XPRESS may use a standard branch-and-bound approach in an attempt to solve optimization problems that are formulated as integer programs, but are often unable to solve even relatively small such problems in a brute force manner before overloading the memory of even the most powerful computers. Even where these solvers incorporate additional algorithms or other techniques in an attempt to reduce the size and complexity of the optimization problem, they are often too slow and require too much processing power to be of practical value. These and other deficiencies make previous systems and methods for optimizing allocation of resources inadequate for many purposes.
According to the present invention, the disadvantages and problems associated with previous optimization systems and methods have been substantially reduced or eliminated.
According to one embodiment of the present invention, a system for optimizing the allocation of a resource includes an optimizer file containing resource allocation data including a demand for allocation of the resource, a plurality of bids for the resource, and a plurality of reserve bids for the resource. A solver receives an integer program and generates an LP relaxation solution to the integer program. An optimizer engine coupled to the file and to the solver receives the data and the LP relaxation solution and generates an enhanced integer program that includes at least one cut according to the data. The cut includes a lifted cover inequality of a specified general form that the LP relaxation solution violates. A parameter associated with the lifted cover inequality is determined according to a first heuristic. The solver generates a solution to the enhanced integer program that optimizes the allocation of the resource subject to the demand, bids, and reserve bids.
In another embodiment of the present invention, the engine constructs a maximization problem of a specified general form according to the data, bids, and reserve bids and communicates the problem. The problem incorporates at least one special ordered set. The solver receives the problem and determines a cover according to the problem. In yet another embodiment, the present invention may provide the solver with priorities to further improve the optimization process.
The system and method of the present invention provide numerous important technical advantages. The present invention allows the allocation of a resource, such as one or more shipping lanes for example, to be optimized quickly, efficiently, and accurately relative to standard xe2x80x9cbrute forcexe2x80x9d approaches for solving integer programs. Furthermore, the present invention may optimize the allocation of a resource where previous systems and methods are unable to provide any solution due to insufficient computer memory or other limitations. One or more cuts generated according to one embodiment of the present invention allow an associated solver to generate a suitable solution to the enhanced integer program quickly, efficiently, and accurately relative to previous techniques. In other embodiments, one or more special ordered sets may be incorporated into a maximization problem used in determining a cover, incorporated into a cover inequality to generate a cut, or incorporated into a lifted cover inequality to generate a cut. Cuts may be particularly effective in combination with priorities generated according to the present invention. Other important technical advantages are readily apparent to those skilled in the art.